Segment Tree

데이터의 구간에 대한 문제가 주어졌을 때 이를 Tree로 가공하여 이후 주어지는 Query들을 log(N) 시간으로 처리하는 알고리즘

• 데이터 배열(이진 트리인 경우)

  n번째 index의 왼쪽 자식은 n*2, 오른쪽 자식은 n*2 + 1 번째이다. root의 index는 1이다. 데이터 크기: 넉넉하게 N*4로 설정한다. (길이가 1인 leaf node가 N보다 큰 2의 제곱수 중 최솟값 (28 → 32), 따라서 총 크기는 이의 두배임.)

• 초기화 함수 O(N)

  함수 매개변수: 현재 index, 시작 범위, 끝 범위 리턴값: 규칙 → 배열에 들어가는 값

  루트 노드부터 시작해 리프 노드까지 재귀하며, 왼쪽 자식은 범위의 왼쪽 절반을, 오른쪽 자식은 범위의 오른쪽 절반을 사용한다.

  각 노드에서는 왼쪽 자식의 계산 값과 오른쪽 자식의 계산 값을 이용해 규칙에 따라 현재의 값을 계산한다. 리프 노드에서는 범위의 array를 사용해 규칙에 따라 배열에 들어갈 값을 계산한다.

• 갱신 함수 O(logN)

  함수 매개변수: 현재 index, 시작 범위, 끝 범위, 갱신 index, 갱신 값 리턴값: (-)

  루트 노드부터 시작해 리프 노드까지 재귀하며, 왼쪽 자식은 범위의 왼쪽 절반을, 오른쪽 자식은 범위의 오른쪽 절반을 사용한다.

  현재 범위 안에 갱신 index가 포함되면, 규칙에 따라 값을 갱신한다.

• 쿼리 함수 O(logN)

  함수 매개변수: 현재 index, 시작 범위, 끝 범위, Query 시작 범위, Query 끝 범위 리턴값: 규칙 → 배열에 들어가는 값

  각 노드에서는 현재의 범위가 Query의 범위를 벗어난다면 0(규칙→문제에 쓸모없는 값)을 리턴한다. 현재의 범위가 Query의 범위 안쪽이라면 배열에 저장된 값을 리턴한다. 현재의 범위가 Query의 범위를 걸친다면 자식 노드를 호출하고 리턴값으로 규칙에 따라 답을 구한다.

  루트 노드로부터 시작해 리프 노드까지 재귀하며, 왼쪽 자식은 범위의 왼쪽 절반을, 오른쪽 자식은 범위의 오른쪽 절반을 사용한다.